/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core
// Copyright (c) 2014.  All Rights Reserved
//
// File:		AETMap.inl
// Author:		Gianluca Belardelli
// Date:		24/09/2013
//
/////////////////////////////////////////////////////////////////////////
template <class TKEY, class TVALUE>
AETMap<TKEY,TVALUE>::AETMap( unsigned int uiTableSize )
{
    AEASSERT( uiTableSize > 0 );

    m_uiTableSize = uiTableSize;
    m_uiSize = 0;
    m_uiIndex = 0;
    m_lpItem = NULL;
    m_lplpTable = new AEHashItem*[ m_uiTableSize ];
    memset( m_lplpTable, 0, m_uiTableSize*sizeof( AEHashItem* ) );
}

template <class TKEY, class TVALUE>
AETMap<TKEY,TVALUE>::~AETMap()
{
    RemoveAll();
    delete [] m_lplpTable;
}

template <class TKEY, class TVALUE>
unsigned int AETMap<TKEY,TVALUE>::GetSize() const
{
    return m_uiSize;
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::IsEmpty() const
{
    return m_uiSize == 0;
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::SetAt( const TKEY &tKey, const TVALUE &tValue )
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction( tKey );
    AEHashItem *lpItem = m_lplpTable[ uiIndex ];

    // search for item in list associated with key
    while ( lpItem )
    {
        if ( tKey == lpItem->m_tKey )
        {
            // item already in hash table
            return false;
        }
        lpItem = lpItem->m_lpNext;
    }

    // add item to beginning of list
    lpItem = new AEHashItem;
    lpItem->m_tKey = tKey;
    lpItem->m_tValue = tValue;
    lpItem->m_lpNext = m_lplpTable[ uiIndex ];
    m_lplpTable[ uiIndex ] = lpItem;
    m_uiSize++;

    return true;
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::GetAt( const TKEY& tKey, TVALUE& tValue ) const
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction( tKey );
    AEHashItem *lpItem = m_lplpTable[ uiIndex ];

    // search for item in list associated with key
    while ( lpItem )
    {
        if ( tKey == lpItem->m_tKey )
        {
            // item is in hash table
            tValue = lpItem->m_tValue;
            return true;
        }
        lpItem = lpItem->m_lpNext;
    }

    return false;
}

template <class TKEY, class TVALUE>
TVALUE AETMap<TKEY,TVALUE>::operator[] ( const TKEY &tKey ) const
{
    unsigned int uiIndex = HashFunction( tKey );
    AEHashItem *lpItem = m_lplpTable[ uiIndex ];

    // search for item in list associated with key
    while ( lpItem )
    {
        if ( tKey == lpItem->m_tKey )
        {
            // item is in hash table
            return lpItem->m_tValue;
        }
        lpItem = lpItem->m_lpNext;
    }

	return NULL;
}

template <class TKEY, class TVALUE>
TVALUE &AETMap<TKEY,TVALUE>::operator[] ( const TKEY &tKey )
{
    unsigned int uiIndex = HashFunction( tKey );
    AEHashItem *lpItem = m_lplpTable[ uiIndex ];

    // search for item in list associated with key
    while ( lpItem )
    {
        if ( tKey == lpItem->m_tKey )
        {
            // item is in hash table
            return lpItem->m_tValue;
        }
        lpItem = lpItem->m_lpNext;
    }

	return NULL;
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::RemoveAt( const TKEY &tKey )
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction( tKey );
    AEHashItem *lpItem = m_lplpTable[ uiIndex ];

    if ( !lpItem )
    {
        return false;
    }
    else if ( tKey == lpItem->m_tKey )
    {
        // item is at front of list, strip it off
        AEHashItem *lpSave = lpItem;
        m_lplpTable[ uiIndex ] = lpItem->m_lpNext;
        delete lpSave;
        m_uiSize--;
        return true;
    }
    else
    {
        // search for item in list
        AEHashItem *lpPrev = lpItem;
        AEHashItem *lpCurr = lpItem->m_lpNext;
        while ( lpCurr && tKey != lpCurr->m_tKey )
        {
            lpPrev = lpCurr;
            lpCurr = lpCurr->m_lpNext;
        }
        if ( lpCurr )
        {
            // found the item
            lpPrev->m_lpNext = lpCurr->m_lpNext;
            delete lpCurr;
            m_uiSize--;
            return true;
        }
    }

    return false;
}

template <class TKEY, class TVALUE>
void AETMap<TKEY,TVALUE>::RemoveAll()
{
    if( m_uiSize > 0 )
    {
        for( unsigned int uiIndex = 0; uiIndex < m_uiTableSize; uiIndex++ )
        {
            while( m_lplpTable[uiIndex] )
            {
                AEHashItem *lpSave = m_lplpTable[uiIndex];
                m_lplpTable[uiIndex] = m_lplpTable[uiIndex]->m_lpNext;
                delete lpSave;

                if( --m_uiSize == 0 )
                    return;
            }
        }
    }
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::GetFirst( TKEY &tKey, TVALUE &tValue )
{
    if( m_uiSize > 0 )
    {
        for( m_uiIndex = 0; m_uiIndex < m_uiTableSize; m_uiIndex++ )
        {
            if( m_lplpTable[m_uiIndex] )
            {
                m_lpItem = m_lplpTable[m_uiIndex];
                tKey = m_lpItem->m_tKey;
                tValue = m_lpItem->m_tValue;
                return true;
            }
        }
    }

    return false;
}

template <class TKEY, class TVALUE>
bool AETMap<TKEY,TVALUE>::GetNext( TKEY& tKey, TVALUE& tValue )
{
    if( m_uiSize > 0 )
    {
        m_lpItem = m_lpItem->m_lpNext;
        if ( m_lpItem )
        {
            tKey = m_lpItem->m_tKey;
            tValue = m_lpItem->m_tValue;
            return true;
        }
        
        for( m_uiIndex++; m_uiIndex < m_uiTableSize; m_uiIndex++ )
        {
            if( m_lplpTable[m_uiIndex] )
            {
                m_lpItem = m_lplpTable[m_uiIndex];
                tKey = m_lpItem->m_tKey;
                tValue = m_lpItem->m_tValue;
                return true;
            }
        }
    }

    return false;
}

template <class TKEY, class TVALUE>
unsigned int AETMap<TKEY,TVALUE>::HashFunction( const TKEY &tKey ) const
{
    static double s_dHashMultiplier = 0.5*( AEMath::Sqrt( 5.0 ) - 1.0 );

    unsigned int uiKey = (unsigned int)tKey;
    double dFraction = AEMath::Mod( s_dHashMultiplier*uiKey, 1.0 );

    return (unsigned int)AEMath::Floor( m_uiTableSize*dFraction );
}

